#include <iostream>
#include <cassert>
using namespace std;
template<class T>
class List
{
	struct ListNode // 链表
	{
		T data;
		ListNode* next;
	};
private:
	ListNode* m_list;
	int m_size;
public:
	List()
	{
		m_list = new ListNode;
		m_list->data = 0;
		m_list->next = m_list; // 自己指向自己
		m_size = 0;
	}
	List(const T data) : List()
	{
		ListNode* node = new ListNode;
		node->data = data;
		node->next = m_list;
		m_list->next = node;
		m_size++;
	}
	~List()
	{
		ListNode* pr = nullptr;
		ListNode* it = m_list->next;
		while (it != m_list) // it 删除下标为 0 的结点
		{
			pr = it;
			it = it->next;
			delete pr;
		}
		delete it; // 删除头结点
		m_list = nullptr;
		m_size = -1;
	}
public:
	void push_back(const T data)
	{
		ListNode* node = new ListNode;
		node->data = data;
		node->next = m_list;
		if (empty())
		{
			m_list->next = node;
			m_size++;
			return;
		}
		ListNode* current = m_list;
		while (current->next != m_list)
		{
			current = current->next;
		}
		current->next = node;
		m_size++;
	}
	void pop_back()
	{
		if (empty())
			return;
		ListNode* current = m_list->next;
		ListNode* pre = m_list;
		while (current->next != m_list)
		{
			current = current->next;
			pre = pre->next;
		}
		pre->next = m_list;
		delete current;
		m_size--;
	}
	void push_front(const T data)
	{
		ListNode* node = new ListNode;
		node->data = data;
		node->next = m_list->next;
		m_list->next = node;
		m_size++;
	}
	void pop_front()
	{
		if (empty())
			return;
		ListNode* current = m_list->next;
		m_list->next = current->next;
		delete current;
		m_size--;
	}
	void insert(const T data, int pos)
	{
		assert(pos < m_size);
		ListNode* pre = m_list;
		for (int i = 0; i < m_size; ++i)
		{
			pre = pre->next;
		}
		ListNode* node = new ListNode;
		node->data = data;
		node->next = pre->next;
		pre->next = node;
		m_size++;
	}
	void erase(T data)
	{
		ListNode* pre = m_list;
		ListNode* current = m_list->next;
		while (current != m_list)
		{
			if (current->data == data)
			{
				pre->next = current->next;
				delete current;
				m_size--;
				return;
			}
			pre = pre->next;
			current = current->next;
		}
	}
public:
	bool empty()
	{
		return m_list->next == m_list;
	}
	int size()
	{
		return m_size;
	}
	int find(const T data)
	{
		ListNode* current = m_list->next;
		for (int i = 0; i < m_size; ++i)
		{
			if (current->data == data)
				return i;
			current = current->next;
		}
		return -1;
	}
	T& operator[](const int pos)
	{
		assert(pos < m_size);
		ListNode* current = m_list->next;
		for (int i = 0; i < pos; ++i)
		{
			current = current->next;
		}
		return current->data;
	}
};
int main()
{
	List<int> list;
	list.push_front(1);
	list.push_front(2);
	list.push_front(3);
	list.push_front(4);
	list.push_front(5);
	list.push_front(6);
	list.insert(3, 3);
	list.erase(3);
	list.erase(3);
	list.erase(3);

	cout << list.find(1) << endl;
	for (int i = 0; i < list.size(); ++i)
	{
		cout << list[i] << " ";
	}
	return 0;
}
